package com.copa.l496;

import java.util.*;

/**
 * @author copa
 * @createDate 2022-06-10 15:20
 * @function 哈希表法/哈希表+单调栈法
 */
public class Test1 {

    // 哈希表法 这个是我自己想的...这个测试起来比官方解法好...
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums2.length; i++) {
            map.put(nums2[i], i);
        }
        for (int j = 0; j < nums1.length; j++) {
            int num = nums1[j];
            int temp = -1;
            for (int i = map.get(num) + 1; i < nums2.length; i++) {
                if (num < nums2[i]) {
                    temp = nums2[i];
                    break;
                }
            }
            result[j] = temp;
        }
        return result;
    }

    // 哈希表+单调栈法 这个是官方的
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack();
        for (int i = nums2.length - 1; i >= 0; i--) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = map.get(nums1[i]);
        }
        return result;
    }



    public static void main(String[] args) {
        int[] nums1 = {4,1,2};
        int[] nums2 = {1,3,4,2};
        int[] result = new Test1().nextGreaterElement(nums1, nums2);
        System.out.println(Arrays.toString(result));
    }
}
